/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 19182
 * Date: 2025-10-21
 * Time: 19:30
 */
public class AVLTreeTest {

        // ... （上述修正后的代码）

        // 所有测试用例入口
        public static void main(String[] args) {
        test1_NoRotation();       // 1. 无需旋转：自然平衡
        test2_SingleRotateRight();// 2. 单旋转：右单旋（左子树失衡）
        test3_SingleRotateLeft(); // 3. 单旋转：左单旋（右子树失衡）
        test4_DoubleRotateLR();   // 4. 双旋转：LR双旋
        test5_DoubleRotateRL();   // 5. 双旋转：RL双旋
        test6_DuplicateNode();    // 6. 重复节点：插入失败
    }

        /**
         * 测试用例1：无需旋转（插入后自然平衡）
         * 插入序列：50,30,70,20,40,60,80
         * 预期：中序有序，所有节点平衡因子±1或0，树高4
         */
        public static void test1_NoRotation() {
        System.out.println("=== 测试用例1：无需旋转（自然平衡） ===");
        AVLTree tree = new AVLTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int val : values) {
            tree.insert(val);
        }
        System.out.print("中序遍历（预期有序）：");
        tree.Inorder(tree.root); // 输出：20 30 40 50 60 70 80
        System.out.println("\n是否平衡（预期true）：" + tree.isBalanced(tree.root));
        System.out.println("树高（预期3)：" + tree.getHeight(tree.root));
        System.out.println("根节点（预期50）：" + tree.root.val + "\n");
    }

        /**
         * 测试用例2：右单旋（左子树失衡）
         * 插入序列：30,20,10（插入10后，30的bf=-2，20的bf=-1）
         * 预期：旋转后根为20，中序有序，平衡
         */
        public static void test2_SingleRotateRight() {
        System.out.println("=== 测试用例2：右单旋（左子树失衡） ===");
        AVLTree tree = new AVLTree();
        int[] values = {30, 20, 10};
        for (int val : values) {
            tree.insert(val);
        }
        System.out.print("中序遍历（预期有序）：");
        tree.Inorder(tree.root); // 输出：10 20 30
        System.out.println("\n是否平衡（预期true）：" + tree.isBalanced(tree.root));
        System.out.println("树高（预期2）：" + tree.getHeight(tree.root));
        System.out.println("根节点（预期20）：" + tree.root.val + "\n");
    }

        /**
         * 测试用例3：左单旋（右子树失衡）
         * 插入序列：30,40,50（插入50后，30的bf=2，40的bf=1）
         * 预期：旋转后根为40，中序有序，平衡
         */
        public static void test3_SingleRotateLeft() {
        System.out.println("=== 测试用例3：左单旋（右子树失衡） ===");
        AVLTree tree = new AVLTree();
        int[] values = {30, 40, 50};
        for (int val : values) {
            tree.insert(val);
        }
        System.out.print("中序遍历（预期有序）：");
        tree.Inorder(tree.root); // 输出：30 40 50
        System.out.println("\n是否平衡（预期true）：" + tree.isBalanced(tree.root));
        System.out.println("树高（预期2）：" + tree.getHeight(tree.root));
        System.out.println("根节点（预期40）：" + tree.root.val + "\n");
    }

        /**
         * 测试用例4：LR双旋（左子树的右子树失衡）
         * 插入序列：50,30,40（插入40后，50的bf=-2，30的bf=1）
         * 预期：先左旋30，再右旋50，根为40，平衡
         */
        public static void test4_DoubleRotateLR() {
        System.out.println("=== 测试用例4：LR双旋（左子树右失衡） ===");
        AVLTree tree = new AVLTree();
        int[] values = {50, 30, 40};
        for (int val : values) {
            tree.insert(val);
        }
        System.out.print("中序遍历（预期有序）：");
        tree.Inorder(tree.root); // 输出：30 40 50
        System.out.println("\n是否平衡（预期true）：" + tree.isBalanced(tree.root));
        System.out.println("树高（预期2）：" + tree.getHeight(tree.root));
        System.out.println("根节点（预期40）：" + tree.root.val + "\n");
    }

        /**
         * 测试用例5：RL双旋（右子树的左子树失衡）
         * 插入序列：50,70,60（插入60后，50的bf=2，70的bf=-1）
         * 预期：先右旋70，再左旋50，根为60，平衡
         */
        public static void test5_DoubleRotateRL() {
        System.out.println("=== 测试用例5：RL双旋（右子树左失衡） ===");
        AVLTree tree = new AVLTree();
        int[] values = {50, 70, 60};
        for (int val : values) {
            tree.insert(val);
        }
        System.out.print("中序遍历（预期有序）：");
        tree.Inorder(tree.root); // 输出：50 60 70
        System.out.println("\n是否平衡（预期true）：" + tree.isBalanced(tree.root));
        System.out.println("树高（预期2）：" + tree.getHeight(tree.root));
        System.out.println("根节点（预期60）：" + tree.root.val + "\n");
    }

        /**
         * 测试用例6：插入重复节点
         * 插入序列：50,30,50（第二次插入50）
         * 预期：提示“不能插入重复节点”，插入失败，树结构不变
         */
        public static void test6_DuplicateNode() {
        System.out.println("=== 测试用例6：插入重复节点 ===");
        AVLTree tree = new AVLTree();
        tree.insert(50);
        tree.insert(30);
        System.out.print("插入50前中序：");
        tree.Inorder(tree.root); // 输出：30 50
        System.out.println("\n插入重复节点50：");
        tree.insert(50); // 提示“不能插入重复节点!”
        System.out.print("插入后中序（预期不变）：");
        tree.Inorder(tree.root); // 输出：30 50
        System.out.println("\n是否平衡（预期true）：" + tree.isBalanced(tree.root) + "\n");
    }
}
